package io.zhengsh.vvip.leetcode.recall;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q47 {


    class Solution {
        boolean[] vis;

        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> perm = new ArrayList<>();
            vis = new boolean[nums.length];

            Arrays.sort(nums);

            backtrack(nums, res, 0, perm);
            return res;
        }

        private void backtrack(int[] nums, List<List<Integer>> res, int i, List<Integer> perm) {

            if (i == nums.length) {
                res.add(new ArrayList<>(perm));
                return;
            }

            for (int j = 0; j < nums.length; j++) {
                if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {
                    continue;
                }

                perm.add(nums[j]);
                vis[j] = true;
                backtrack(nums, res, i + 1, perm);
                // 回溯
                vis[j] = false;
                perm.remove(i);
            }
        }
    }
}
